package Day2025_03_06;

import java.util.*;

class Pair<K, V> {
    private K key;
    private V value;

    public Pair(K key, V value) {
        this.key = key;
        this.value = value;
    }

    public K getKey() {
        return key;
    }

    public V getValue() {
        return value;
    }
}

public class LeetCode692 {
    public List<String> topKFrequent(String[] words, int k) {
        List<String> list = new ArrayList<>();
        PriorityQueue<Pair<String, Integer>> heap = new PriorityQueue<>((a, b) -> {
            if (a.getValue() == b.getValue()) {
                return b.getKey().compareTo(a.getKey());
            }
            return a.getValue() - b.getValue();
        });
        Map<String, Integer> hash = new HashMap<>();
        for (String str : words)
            hash.put(str, hash.getOrDefault(str, 0) + 1);
        for (Map.Entry<String, Integer> e : hash.entrySet()) {
            heap.offer(new Pair<>(e.getKey(), e.getValue()));
            if (heap.size() > k) heap.poll();
        }
        while (!heap.isEmpty())
            list.add(heap.poll().getKey());
        Collections.reverse(list);
        return list;
    }
}
